đệ quy

Hàm đệ quy gọi lại chính nó để giải quyết bài toán.

Định nghĩa

1. Tính từ:

   • Có tính chất tự quy chiếu, lặp lại chính nó: "đệ quy" mô tả một quá trình, định nghĩa hoặc cấu trúc mà trong đó một phần tử được xác định dựa trên chính các phần tử nhỏ hơn hoặc đơn giản hơn của nó, theo một quy tắc lặp lại.
   • Trong toán học và khoa học máy tính: "đệ quy" chỉ phương pháp giải quyết vấn đề bằng cách chia nhỏ vấn đề thành các phiên bản nhỏ hơn, giống hệt về bản chất, cho đến khi đạt đến trường hợp cơ sở.

2. Danh từ:

   • Phương pháp hoặc quy trình đệ quy: "đệ quy" được dùng để chỉ chính cách thức hoặc kỹ thuật tự quy chiếu này.

Ví dụ sử dụng

• Tính từ:

  • Hàm đệ quy là hàm gọi lại chính nó trong quá trình thực thi. (Hàm đệ quy là hàm tự gọi lại chính nó khi chạy.)
  • Định nghĩa đệ quy của giai thừa: n! = n × (n-1)! với 0! = 1. (Định nghĩa đệ quy của giai thừa: n! = n × (n-1)! và 0! = 1.)

• Danh từ:

  • Đệ quy là một công cụ mạnh mẽ trong lập trình để xử lý các cấu trúc dữ liệu phân cấp. (Đệ quy là một công cụ mạnh trong lập trình để xử lý các cấu trúc dữ liệu phân cấp.)
  • Bài toán này có thể giải bằng đệ quy hoặc vòng lặp. (Bài toán này có thể giải bằng cách tự quy chiếu hoặc dùng vòng lặp.)

Các cách sử dụng nâng cao

• "Hàm đệ quy": hàm tự gọi lại chính nó trong thân hàm.

  • Viết hàm đệ quy tính Fibonacci: fib(n) = fib(n-1) + fib(n-2). (Viết hàm tự quy chiếu để tính Fibonacci.)

• "Cấu trúc đệ quy": cấu trúc dữ liệu mà thành phần của nó chứa chính nó (ví dụ: cây, danh sách liên kết).

  • Cây là một cấu trúc đệ quy vì mỗi nút có thể có các nút con là cây con. (Cây là cấu trúc tự quy chiếu vì mỗi nút có thể có các nút con là cây con.)

Biến thể và từ gần giống

• Đệ quy tuyến tính: đệ quy trong đó mỗi lần gọi chỉ tạo ra một lần gọi đệ quy duy nhất.

  • Hàm giai thừa là ví dụ của đệ quy tuyến tính. (Hàm giai thừa là ví dụ của tự quy chiếu tuyến tính.)

• Đệ quy phi tuyến: đệ quy trong đó một lần gọi tạo ra nhiều lần gọi đệ quy.

  • Hàm Fibonacci là ví dụ của đệ quy phi tuyến. (Hàm Fibonacci là ví dụ của tự quy chiếu phi tuyến.)

Từ đồng nghĩa

• Tự quy chiếu: mô tả quá trình tham chiếu đến chính nó.
• Lặp lại chính nó: hành động lặp lại cấu trúc hoặc quy tắc ban đầu.

Thành ngữ liên quan

• Đệ quy vô hạn: đệ quy không có điểm dừng, dẫn đến lỗi tràn bộ nhớ.
  • Nếu quên trường hợp cơ sở, chương trình sẽ rơi vào đệ quy vô hạn. (Nếu quên trường hợp cơ sở, chương trình sẽ rơi vào tự quy chiếu không dừng.)